package cn.edu.xjtu.work.isAlienSorted;

import java.util.HashMap;
import java.util.Map;

/**
 * 953. 验证外星语词典
 * 
 * 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
 * 
 * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回
 * false。
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/verifying-an-alien-dictionary
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), i);
        }

        for (int i = 0; i < words.length - 1; i++) {
            int len = Math.min(words[i].length(), words[i + 1].length());
            int j = 0;
            for (j = 0; j < len; j++) {
                int flag = map.get(words[i].charAt(j)) - map.get(words[i + 1].charAt(j));
                if (flag > 0) {
                    return false;
                } else if (flag < 0) {
                    break;
                }
            }
            if (j == len && j < words[i].length()) {
                return false;
            }
        }

        return true;
    }
}
